/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-14
 * Time: 17:05
 */
public class Sort {

    //选择排序
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            //最小值的下标
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                //如果待排数据中有小于minIndex下标的，minIndex更新
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            //交换minIndex与待排数据的第一个元素
            swap(arr,i,minIndex);
        }
    }

    //交换数组中的两个数
    private static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //选择排序——优化
    public static void selectSortOptimize(int[] arr) {
        //定义左边界
        int left = 0;
        //定义右边界
        int right = arr.length - 1;

        //左右边界一起移动，但他们相遇时，说明数组排好了
        while (left < right) {
            //最小元素的下标
            int minIndex = left;
            //最大元素的下标
            int maxIndex = left;
            for (int i = left; i <= right; i++) {
                if (arr[i] < arr[minIndex]) {
                    //更新最小值下标
                    minIndex = i;
                }

                if (arr[i] > arr[maxIndex]) {
                    //更新最大值下标
                    maxIndex = i;
                }
            }
            //将最小值放到左边界
            swap(arr,left,minIndex);

            //处理特殊情况：当最大值在left处时，进行最小值的放置时，会把在left处的最大值移到minIndex处
            if (maxIndex == left) {
                maxIndex = minIndex;
            }

            //将最大值放到右边界
            swap(arr,right,maxIndex);

            //缩小左右边界
            left++;
            right--;
        }
    }

    //堆排序
    public static void heapSort(int[] arr) {
        //建堆
        createHeap(arr);
        //进行排序
        int end = arr.length - 1;
        while (end > 0) {
            swap(arr,0,end);
            end--;
            siftDown(arr,0,end);
        }
    }
    //建大堆
    private static void createHeap(int[] arr) {
        for (int parent = (arr.length - 1 -1)/2; parent >= 0; parent--) {
            siftDown(arr,parent,arr.length-1);
        }
    }
    //向下调整
    private static void siftDown(int[] arr,int parent,int size) {
        int child = parent*2 + 1;
        while (child <= size) {
            if (child + 1 <= size && arr[child + 1] > arr[child]) {
                child++;
            }
            if (arr[child] > arr[parent]) {
                swap(arr,child,parent);
            }else {
                break;
            }
            parent = child;
            child = parent*2 + 1;
        }
    }
}
